Binary heap insertion averages constant time

Insert into [binary heap

After adding to the leaf, it needs to swap with the parent until the constraints are met

At worst, tree height O(logN)

But since there are 2^n vertices of depth n?

The probability of having to replace a parent.

(Every time you go forward?) Because it will be 1/2,

Is it a constant if we find the mean?

A little dubious.

The average cost of inserting n elements into an initially empty heap is analyzed, under the assumption that the n! orders in which the n elements can be inserted are equally likely. It is proved that this average, expressed in number of exchanges per insertion, is bounded by a constant about 1.7645.

Merge one element into [binary heap

Since the probability of needing to carry forward for the same reason is 1/2, the average number of carry forward operations is of constant order

---